home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / PowerPlant / DMultiStringLocator / About DMultiStringLocator next >
Text File  |  1996-07-06  |  5KB  |  113 lines
  1. About DMultiStringLocator
  2. =========================
  3. Written July 6, 1996 by Eric Gundrum <eric@teamworks.com>
  4.  
  5. Preface
  6. -------
  7. This document describes the DMultiStringLocator class. It contains these
  8. sections:
  9.  
  10.   - What is DMultiStringLocator
  11.   - Implementation Notes 
  12.   - About the Sample Code
  13.   - Use Restrictions
  14.  
  15.  
  16. What is DMultiStringLocator
  17. ---------------------------
  18. DMultiStringLocator is a C++ class to provide fast searching for one or
  19. more strings. It is an implementation of a table-based algorithm
  20. credited to Aho and Corasick and described in "Practical Algorithms for
  21. Programmers" by Andrew Binstock and John Rex (published in 1995 by
  22. Addison Wesley). 
  23.  
  24. DMultiStringLocator is designed to search for more than one string at a
  25. time. Searching for multiple strings works nearly as fast as searching
  26. for a single string. Using a table-lookup mechanism eliminates any
  27. unnecessary backtracking when a partial match fails, accounting for much
  28. of the speed.
  29.  
  30. This algorithm may not be the fastest available, but it should be
  31. sufficient for most practical problems. It is general enough to be used
  32. when searching for a single string, as well as for more than one in the
  33. same target text.
  34.  
  35.  
  36. Implementation Notes
  37. --------------------
  38. The current implementation expects a list of DSearchString objects when
  39. the DMultiStringLocator object is instantiated. Internal state tables
  40. are built from this list in the constructor. (This allocates memory;
  41. about eight times the combined length of the search strings and at least
  42. two times the alphabet size.) Changing the list requires constructing a
  43. new search object (and its state tables).
  44.  
  45. A DSearchString object, based on PowerPlant's LStr255 class, contains a
  46. ReportFound() virtual member function that must be overridden in a
  47. derived class. ReportFound() is executed for each found string. (This is
  48. a performance bottleneck; keep ReportFound() short and fast.) A
  49. parameter to ReportFound() is the position in the string of the last
  50. character of the found string. Use this value to locate the found
  51. strings after the search phase.
  52.  
  53. A search is initiated with a call to SearchBuffer(), which will search a
  54. RAM-based buffer (by walking a pointer through the buffer). Searching
  55. more data than will fit in one buffer can be accomplished with repeated
  56. calls to SearchBuffer(), but you must deal with a match string that is
  57. split over two buffers.
  58.  
  59. To help handle strings split across the buffer, SearchBuffer() returns
  60. the maximum number of characters which might belong to a string found at
  61. the end of the current buffer. These characters should be included in
  62. the next buffer. However, if these characters also include other
  63. complete strings, those strings will be found twice. 
  64.  
  65. For example, consider searching for 'foobarooba' and 'bar', where the
  66. first buffer ends with 'foobaroo'. SearchBuffer() will return 8,
  67. indicating that the second buffer should begin 8 characters before the
  68. end of the first. However, such as search will find 'bar' twice. This is
  69. a design flaw I have not yet resolved. (It is not significant to my
  70. use.) I suggest working around it by looking for multiple hits on the
  71. same string in a post process phase (by tracking the hit position). Or,
  72. handle it in ReportFound() if performance is not an issue.
  73.  
  74. Another limitation of this implementation is that it searches for a byte
  75. sequence. It does not support case-insensitive searches. However, that
  76. is easily remedied by changing the case of the search strings and input
  77. text.
  78.  
  79. DMultiStringLocator currently relies on a few PowerPlant classes,
  80. including LList, LListIterator, and LString. With a bit of effort, these
  81. classes could be replaced with STL classes. I'll leave that for a future
  82. project.
  83.  
  84.  
  85. About the Sample Code
  86. ---------------------
  87. The sample code consists of the CSearchWindow class to demonstrate the
  88. search engine and a supporting PowerPlant application (PPShell).
  89.  
  90. CSearchWindow builds the search list from user input (in DoSearch()). It
  91. then reads the target file into a buffer and performs a search on that
  92. buffer (in SearchFile()). If the file contains more data, the process is
  93. repeated until all is read. Note that SearchFile() will overlay the
  94. buffer ends to a deal with match strings split over two buffers. 
  95.  
  96. CSearchString is an important support class used by CSearchWindow.
  97. Derived from DSearchString, CSearchString demonstrates how to minimally
  98. collect the results of a search with the ReportFound() function. Here
  99. ReportFound() is used to count the number of hits. It also tracks the
  100. position of found strings to prevent reporting them twice. 
  101.  
  102.  
  103. Use Restrictions
  104. ----------------
  105. I place no restrictions on how this code may be used or distributed. I
  106. ask only that my copyright statement be retained in the source files of
  107. all derivative works. (I put a lot of work into this class and I want
  108. people to know who did it.)
  109.  
  110. If you have comments or want to report bugs, send mail to
  111. <eric@teamworks.com>.
  112.  
  113.